package com.yiwenup.leetcode.hot;

import java.util.ArrayList;
import java.util.List;

/**
 * @PROJECT struct-algorithm
 * @PACKAGE com.yiwenup.leetcode.hot
 * @Author yiwenup
 * @Date 2022-02-28 10:04:11
 * <p>
 * @DESCRIPTION https://leetcode-cn.com/problems/generate-parentheses/
 */
public class No022 {
    private List<String> res = new ArrayList<>();

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了74.99%的用户
     * 内存消耗：41.3 MB, 在所有 Java 提交中击败了20.18%的用户
     */
    public List<String> generateParenthesis(int n) {
        generateParenthesis("", n, n);
        return res;
    }

    private void generateParenthesis(String tmp, int left, int right) {
        if (left == 0 && right == 0) {
            res.add(tmp);
            return;
        }

        if (left == right) {
            // 如果左边括号剩余数量等于右边括号剩余数量，则优先拼接左边括号剩余数量
            generateParenthesis(tmp + "(", left - 1, right);
        } else if (left < right) {
            if (left > 0) {
                generateParenthesis(tmp + "(", left - 1, right);
            }
            generateParenthesis(tmp + ")", left, right - 1);
        }
    }
}
